package com.wd.study.algorithm;

/**
 * 二分查找<BR>
 *
 * @author w4425
 * @version [V2.0.0, 2021/3/12]
 * @since V2.0.0
 */
public class Binary {
    /**
     * 有序的序列，每次都是以序列的中间位置的数来与待查找的关键字进行比较，每次缩小一半的查找范围，直到匹配成功。
     * <p>
     * 一个情景：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
     * 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
     * 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
     * ————————————————
     * [优点] 比较次数少，查找速度快，平均性能好；
     * [缺点] 要求待查表为有序表，且插入删除困难。
     * [因此] 折半查找方法适用于不经常变动而查找频繁的有序列表。
     * 使用条件：查找序列是顺序结构，有序。
     */
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 22, 23, 43, 66};
        int key = 5;
        int position = recursionBinarySearch(arr, key, 0, arr.length - 1);
        System.out.println("key = " + key + " ; position = " + position + "; arr[i] = " + arr[position]);
        System.out.println("-----------");
        key = 9;
        int position2 = commonBinarySearch(arr, key);
        System.out.println("key = " + key + " ; position2 = " + position2 + "; arr[i] = " + arr[position2]);
    }

    /**
     * 递归
     *
     * @param arr  有序数组
     * @param key  查找关键字
     * @param low  表起始位置
     * @param high 表结束位置
     * @return 返回其位置
     */
    public static int recursionBinarySearch(int[] arr, int key, int low, int high) {
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        // 中间位置
        int middle = (low + high) / 2;
        if (arr[middle] > key) {
            //比关键字大则关键字在左区域
            return recursionBinarySearch(arr, key, low, middle - 1);
        } else if (arr[middle] < key) {
            //比关键字大则关键字在右区域
            return recursionBinarySearch(arr, key, middle + 1, high);
        } else {
            return middle;
        }
    }

    /**
     * 非递归 while
     *
     * @param arr 有序数组
     * @param key 查找关键字
     * @return 返回其位置
     */
    public static int commonBinarySearch(int arr[], int key) {
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        while (low <= high) {
            middle = (low + high) / 2;
            if (arr[middle] > key) {
                high = middle - 1;
            } else if (arr[middle] < key) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

}
